package com.jhy.suixianglu.shuangzhizhen.daima20230118;

/**
 * 给你一个字符串 s ，请你反转字符串中 单词 的顺序。
 * <p>
 * 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。
 * <p>
 * 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
 * <p>
 * 注意：输入字符串 s中可能会存在前导空格、
 * 尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/reverse-words-in-a-string
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ReverseWords {
    public String reverseWords(String s) {
        // 首先将字符串当中的前后的空格以及中间多余的空格给消除掉
        char[] chars = s.toCharArray();
        chars = removeExtraSpaces(chars);
        // 将字符串进行反转
        reverse(chars,0,chars.length-1);
        // 将单独的单词逐个进行反转
        reverseEachWord(chars);
        return  new String(chars);
    }

    private void reverseEachWord(char[] chars) {
        int start = 0;
        for (int end = 0; end <= chars.length ; end++) {
            if(end == chars.length || chars[end] == ' '){
                reverse(chars,start,end-1);
                // 这个end+1 不应该在if的外面 因为是start是针对现在的end的前面一个位置
                start = end+1;
            }

        }
    }

    private void reverse(char[] removeExtraSpaces, int left, int right) {
        while (left<right){
            char temp = removeExtraSpaces[left];
            removeExtraSpaces[left] = removeExtraSpaces[right];
            removeExtraSpaces[right] = temp;
            left++;
            right--;
        }
    }


    private char[] removeExtraSpaces(char[] chars) {
        // 定义一个慢指针 慢指针为我们的新的数组的下标
        int slow = 0;
        for (int fast = 0; fast < chars.length; fast++) {
            // fast的位置上不为空 是整个方向进行赋值的前提 为空就不管它了
            if(chars[fast] != ' '){
                // 这里我们是以每一个单词为一个循环
                if (slow != 0) {
                    // 因为slow是受限于fast的 所以我们直接将下一个单词的前面加上这个空格
                    chars[slow++] = ' ';
                }
                // 对下面的每一个部分的整个单词进行操作
                while(fast < chars.length && chars[fast] != ' '){
                    chars[slow++] = chars[fast++];
                }
            }
        }
        char[] newChars = new char[slow];
        System.arraycopy(chars,0,newChars,0,slow);
        return newChars;
    }
}
